*90 minut na vypracování řešení
*
1. (10 bodů) Na vstupu je posloupnost n celých čísel. Zjistěte, zdali existuje dvojice celých čísel a ≤ b taková, že jak a-1 tak b+1 v posloupnosti leží, zatímco žádné z čísel v (uzavřeném) intervalu ‹a,b› nikoliv. Pokud taková "souvislá mezera" v posloupnosti existuje, vraťte dvojici a,b takovou, že a i b jsou minimální hodnoty, splňující uvedenou podmínku. Pokud neexistuje, vraťte hodnotu None.
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí vzhledem k délce vstupní posloupnosti.
(a)** Popište algoritmus:** programový kód v Pythonu je vítán, ale není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte žádné netriviální datové struktury (typu zásobník, fronta, halda, slovník), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.
(b) Zdůvodněte **správnost **algoritmu.
(c) Odvoďte časovou a prostorovou složitost (v nejhorším případě).
Příklad:
vstup: 22 8 5 2000 6 5 20 100000 7 15 20 6
výstup: 9 14
Poznámka: Úlohu lze vyřešit s časovou i prostorovou složitostí 0(n). Netriviální počet bodů bude ovšem udělen i za méně efektivní řešení.
**2. (10 bodů) **Na vstupu je zadán
binární vyhledávací strom (BVS), v jehož vrcholech jsou uložena celá čísla
a dvě celá čísla d ≤ h .
Navrhněte efektivní algoritmus, který ze zadaného BVS
**odstraní **všechny **vrcholy **s hodnotami < d nebo > h
a vrátí odkaz na kořen výsledného BVS.
Na výstupu tedy bude BVS, v němž jsou uloženy právě ty hodnoty ze vstupního BVS, které leží v uzavřeném intervalu ‹d,h›.
Poznámka: Ani BVS na vstupu, ani BVS na výstupu nemusí být nutně vyvážený.
(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu uvedenou **níže **a váš kód opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte časovou složitost.
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def __init__(self, info = None, levy = None, pravy = None):
self.info = info # data
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def zuzeniBVS(koren: VrcholBinStromu, d: int, h: int) -> VrcholBinStromu:
"""
koren : kořen zadaného binárního vyhledávacího stromu
vrátí : kořen zúženého binárního vyhledávacího stromu
"""
3. Odpovězte na otázky, své odpovědi vždy zdůvodněte.
(a) (5 bodů) Dokažte nebo vyvraťte každé z následujících tvrzení:
pro libovolné tři funkce f, g, h: N → R<sup>+</sup> platí
jestliže * f = O( g ) * a g = O( h ) , potom f · g = O( h )
pro libovolné tři funkce f, g, h: N → R<sup>+</sup> platí
jestliže f = O( g ) a g = O( h ) , potom * f · g = O( h<sup>2</sup> )*
pro libovolné tři funkce f, g, h: **N → R<sup>+</sup> **platí
jestliže f = O( g ) a * g = O( h )* , potom * f · g = O( h<sup>3</sup> )*
Svoji odpověď zdůvodněte, tj. tvrzení dokažte (pokud platí) či sestrojte protipříklad (pokud neplatí). Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.
(b) (5 bodů) Budeme pracovat s minimalistickou binární haldou (v kořeni je minimum). Potřebujeme implementovat operaci zrušení zadaného prvku z haldy:
vstupem algoritmu bude halda a odkaz na jeden její vrchol x, jehož hodnotu chceme zrušit
výstupem bude patřičně změněná halda.
V následujícím popisu si haldu představujeme v podobě binárního stromu. Požadovaný algoritmus jsme implementovali takto:
Odebereme z haldy její poslední vrchol, tzn. vrchol ležící v poslední vrstvě haldy co nejvíce vpravo.{: style="list-style-type:decimal"}
Hodnotou tohoto odebraného vrcholu nahradíme hodnotu ve vrcholu x.{: style="list-style-type:2"}
Dále postupujeme stejně, jako při standardní operaci odebrání minima z haldy:
novou hodnotu vrcholu x porovnáme s hodnotami v obou jeho dětech
v případě potřeby vyměníme s menším z obou dětí
a obdobným způsobem postupujeme dále haldou směrem dolů, dokud je zapotřebí vyměňovat hodnoty.{: style="list-style-type:3"}
**Rozhodněte, zda je **popsaná implementace požadovaného algoritmu korektní. Svoje tvrzení zdůvodněte.